It will be recalled that channel “block encoding” consists, when the “codewords” sent to a receiver or recorded on a data carrier are formed, of introducing a certain level of redundancy in the data. More particularly, by means of each codeword, the information is transmitted that is initially contained in a predetermined number k of symbols taken from an “alphabet” of finite size q; on the basis of these k information symbols, calculation is made of a number n>k of symbols belonging to that alphabet, which constitute the components of the codewords: v=(v1,v2, . . . ,vn). The set of codewords obtained when each information symbol takes some value in the alphabet constitutes a sort of dictionary referred to as a “code” of “dimension” k and “length” n.
When the size q of the “alphabet” is a power of a prime number, the alphabet can be given the structure of what is known as a “Galois field”, denoted Fq, of which the non-zero elements may conveniently be identified as each being equal to γi for a corresponding value of i, where i=1, . . . ,q−1, and where γ is a primitive (q−1)th root of unity in Fq.
In particular, certain codes, termed “linear codes” are such that any linear combination of codewords (with the coefficients taken from the alphabet) is still a codeword. These codes may conveniently be associated with a matrix H of dimension (n−k)×n, termed “parity-check matrix”: a word v of given length n is a codeword if, and only if, it satisfies the relationship: H·vT=0 (where the exponent T indicates the transposition); the code is then said to be “orthogonal” to the matrix H.
At the receiver, the associated decoding method then judiciously uses this redundancy to detect any transmission errors and if possible to correct them. There is a transmission error if the difference e between a received word r and the corresponding codeword v sent by the transmitter is non-zero.
More particularly, the decoding is carried out in two main steps.
The first step consists of associating an “associated codeword” with the received word. To do this, the decoder first of all calculates the “error syndromes vector” s=H·rT=H·eT of length (n−k) (in the context of the present invention, no difference is made between the term “word” and the term “vector”). If the syndromes are all zero, it is assumed that no transmission error has occurred, and the “associated codeword” will then simply be taken to be equal to the received word. If that is not the case, it is thereby deduced that the received word is erroneous, and calculations are then performed that are adapted to estimate the value of the error e; in other words, these calculations provide an estimated value ê such that (r−ê) is a codeword, which will then constitute the “associated codeword”. Usually, this first step of the decoding is divided into two distinct sub-steps: a first so-called “error locating” sub-step, during which the components of the received word are determined of which the value is erroneous, and a second so-called “error correction” sub-step, during which an estimation is calculated of the transmission error affecting those components.
The second step simply consists in reversing the encoding method. In the ideal situation in which all the transmission errors have been corrected, the initial information symbols are thereby recovered.
It will be noted that in the context of the present invention, reference will often be made to “decoding” for brevity, to designate solely the first of those steps, it being understood that the person skilled in the art is capable without difficulty of implementing the second step.
The objective usually given to the decoding is to associate with the received word the codeword situated at the shortest Hamming distance from this received word, the “Hamming distance” being, by definition, the number of places where two words of the same length have a different symbol. The shortest Hamming distance between two different codewords of a code is termed the “minimum distance” d of that code. This is an important parameter of the code. More particularly, it is in principle possible to find the position of the possible errors in a received word, and to provide the correct replacement symbol (i.e. that is identical to that sent by the transmitter) for each of those positions, each time the number of erroneous positions is at most equal to INT[(d−1)/2] (where “INT” designates the integer part) for a code of minimum distance d (for certain error configurations, it is sometimes even possible to achieve better). However, in all cases, the concern is not with a possibility in principle, since it is often difficult to develop a decoding algorithm achieving such performance. It should also be noted that, when the chosen algorithm manages to propose a correction for the received word, that correction is all the more reliable (at least, for most transmission channels) the smaller the number of positions it concerns.
Among known codes, “Reed-Solomon” codes may be cited, which are reputed for their efficiency. They are linear codes, of which the minimum distance d is equal to (n−k+1). The parity-check matrix H of the Reed-Solomon code of dimension k and length n (where n is necessarily equal to (q−1) or to a divisor of (q−1)) is a matrix with (n−k) lines and n columns, which has the structure of a Vandermonde matrix. This parity-check matrix H, which may be defined for example by taking Hij=αi(j−1) (1≦i≦n−k, 1≦j≦n), where α is an nth root of unity in Fq; it is then possible to label the component vj, where 1≦i≦n, of any codeword v=(v1,v2, . . . ,vn) by means of the element α(j−1) of Fq; it is for this reason that a set such as (1,α,α2, . . . ,αn−1) is termed “locating set” of the Reed-Solomon code. For certain particular needs, it is also possible to define “extended” or “shortened” Reed-Solomon codes of different length from the “normal” lengths which have just been mentioned. Finally, it is possible to “modify” the Reed-Solomon codes in the following manner: a diagonal matrix P of type n×n, is chosen of which all the diagonal elements are non-zero, and the matrix HP=H·P is defined, where H is the parity-check matrix for the “standard” Reed-Solomon code defined above; a word belongs to this “modified” code if, and only if, it is orthogonal to HP; the properties of such a modified code are essentially the same as those of the original “standard” code.
As mentioned above, the step of a method of decoding during which a “codeword associated with the received word” is calculated is divided into two sub-steps: the first sub-step is an “error locating” step serving to identify in the received word the components whose value is erroneous; the second sub-step consists then of calculating the corrected value of those erroneous components.
For the decoding of Reed-Solomon codes, as regards error locating, use is usually made of the algorithm known as the “Berlekamp-Massey” algorithm, which will now be briefly described: firstly a matrix S is constructed, termed “syndromes matrix”, of which each element is a certain component of the error syndromes vector s=H·rT=H·eT; next a vector Λ is sought such that Λ·S=0, then an “error locating polynomial” Λ(Z) is formed of which the coefficients are components of the vector Λ; the inverses of the roots of that polynomial Λ(Z) are then, among the elements ωi (where i=1, . . . ,n) of the locating set, those which label the erroneous components of the received word r.
As regards the error correction, use is usually made of the algorithm known as the “Formey” algorithm which will now be briefly described. The error calculating polynomial Ω(Z)=Λ(Z)S(Z) modulo Zn−k is constructed, where
      S    ⁡          (      Z      )        =            ∑              i        =        0                    n        -        k        -        1              ⁢                  s        i            ⁢              Z        i            and the si are the components of the error syndromes vector s; the errors are then given, for i=1, . . . ,n, by:
      e    i    =      {                                        0                                if                                                              Λ                ⁡                                  (                                      ω                    i                                          -                      1                                                        )                                            ≠              0                                                                          -                                                Ω                  ⁡                                      (                                          ω                      i                                              -                        1                                                              )                                                                                        p                    i                                    ⁢                                                            Λ                      ′                                        ⁡                                          (                                              ω                        i                                                  -                          1                                                                    )                                                                                                                if                                                              Λ                ⁡                                  (                                      ω                    i                                          -                      1                                                        )                                            =              0                                          ,      where Λ′(Z) designates the derivative of Λ(Z), and pi is equal to 1 for a “standard” Reed-Solomon code and at the diagonal element in position (i,i) of the matrix P for a modified code (see above).
For more details on Reed-Solomon codes, and in particular the algorithms of Berlekamp-Massey and of Formey, reference may for example be made to the work by R. E. Blahut entitled “Theory and practice of error-control codes”, Addison-Wesley, Reading, Mass., 1983;
For modern information carriers, for example on computer hard disks, CDs (“compact discs”) and DVDs (“digital video discs”), it is sought to increase the density of information. When such a carrier is affected by a physical defect such as a scratch, a high number of information symbols may be rendered unreadable. This problem may nevertheless be remedied by using a very long code. However, as indicated above, the length n of the words in Reed-Solomon codes is less than the size q of the alphabet of the symbols. Consequently, if a Reed-Solomon code is desired having codewords of great length, high values of q must be envisaged, which leads to costly implementations in terms of calculation and storage in memory. Moreover, high values of q are sometimes ill-adapted to the technical application envisaged. For this reason, it has been sought to build codes which naturally provide words of greater length than Reed-Solomon codes without however requiring a longer alphabet.
In particular so-called “algebraic geometric codes” or “Goppa geometric codes” have recently been proposed (see for example “Algebraic Geometric Codes” by par J. H. van Lint, in “Coding Theory and Design Theory” 1st part, IMA Volumes Math. Appl., volume 21, Springer-Verlag, Berlin, 1990). These codes are constructed from a set of n pairs (x,y) of symbols belonging to a chosen Galois field Fq; this set of pairs constitutes the locating set of the algebraic geometric code. In general terms, there is an algebraic equation with two unknowns X and Y such that the pairs (x,y) of that locating set are all solutions of that algebraic equation. The values of x and y of these pairs may be considered as coordinates of “points” Pj (where j=1, . . . ,n) forming an “algebraic curve”.
An important parameter of such a curve is its “genus” g. In the particular case where the curve is a simple straight line (the genus g is then zero), the algebraic geometric code reduces to a Reed-Solomon code. For given q and g, certain algebraic curves, termed “maximum”, make it possible to achieve a length equal to (q+2 g√{square root over (q)}), which may be very high; for example, with an alphabet size of 256 and a genus equal to 120, codewords are obtained of length 4096.
In the context of the present invention, a very general class of algebraic geometric codes is concerned: these codes, of which an example described in detail will be found below, are defined on an algebraic curve represented by an equation f(X,Y)=0 withf(X,Y)=Xb+cYa+ΣcijXiYj,where c≠0 and the cij are elements of Fq, a and b are strictly positive mutually prime integers, and where the sum only applies to the integers i and j which satisfy ai+bj<ab. This form of equation is referred to as “C(a,b)”. For such a code, a parity-check matrix is conventionally defined in the following manner. With every monomial YtXu, where t and u are positive integers or zero, a “weight” is associated (see below for details). If, for an integer ρ>0, there is at least one monomial of which the weight is ρ, it is said that ρ is an “achievable” weight. Let ρ1<ρ2< . . . <ρn−k be the (n−k) smallest achievable weights, and let hi (where i=1, . . . ,n−k) be a monomial of weight ρi. The element in line i and column j of the parity-check matrix is equal to the monomial hi evaluated at the point Pj (where, it may be recalled, j=1, . . . ,n ) of the algebraic curve. Each point Pj then serves to identify the jth component of any codeword. A code having such a parity-check matrix is termed a “one-point” code since its parity-check matrix is obtained by evaluating (at the n points Pj) functions (the monomials hi) which have poles only at a single point, i.e. the point at infinity.
Algebraic geometric codes are advantageous as to their minimum distance d, which is at least equal to (n−k+1−g), and, as has been said, as to the length of the codewords, but they have the drawback of requiring decoding algorithms that are rather complex, and thus rather expensive in terms of equipment (software and/or hardware) and processing time. This complexity is in fact greater or lesser according to the algorithm considered, a greater complexity being in principle the price to pay for increasing the error correction capability of the decoder (see for example the article by Tom Høholdt and Ruud Pellikaan entitled “On the Decoding of Algebraic-Geometric Codes”, IEEE Trans. Inform. Theory, vol. 41 no. 6, pages 1589 to 1614, November 1995). Generally, the higher the genus g of the algebraic curve used, the greater the length of the codewords, but also the greater the complexity of the decoding.
Various error locating algorithms are known for algebraic geometric codes (defined on a curve of non-zero genus).
Such an algorithm, termed “basic” algorithm, has been proposed by A. N. Skorobogatov and S. G. Vlâdut in the article entitled “On the Decoding of Algebraic-Geometric Codes”, IEEE Trans. Inform. Theory, vol. 36 no. 5, pages 1051 to 1060, November 1990). This algorithm will now be described briefly:                a) a “syndromes matrix” S, of dimension (n−k)×(n−k), is constructed, of which each coefficient Sij, where j is less than or equal to a “boundary” value w(i), is equal to a linear combination judiciously chosen of the elements sv (v=1,2, . . . ,n−k) of the syndrome s, the coefficients Sij beyond the boundary remaining indeterminate,        b) the system of linear equations is considered        
                    ∑                  i          =          1                β            ⁢                        l          i                ⁢                  S          ij                      =    0    ,            for      ⁢                          ⁢      j        =    1    ,  2  ,  …  ⁢          ,      w    ⁡          (      β      )        ,where the unknowns li belong to the same alphabet of symbols as the elements of the codewords, and where β is an integer between 1 and (n−k) such that the system permits a non-trivial solution (that is to say a solution in which the coefficients li are not all zero), and determining the values of the coefficients li corresponding to the smallest possible value of β, which will be denoted λ; and                c) calculating the zeros of the “error-locating polynomial”        
            Λ      ⁡              (                  x          ,          y                )              ≡                  ∑                  i          =          1                λ            ⁢                        l          i                ⁢                              h            i                    ⁡                      (                          x              ,              y                        )                                ,these zeros comprising all the pairs (x,y) corresponding to positions of the received word for which the component in that position has suffered a transmission error.
Skorobogatov and Vlâdut have also proposed, in the same article cited above, a “modified” version of the “basic” algorithm, which generally enables a higher number of errors to be corrected that the “basic” algorithm.
Algorithms are also known which operate using an iterative principle: each new iteration of such an algorithm invokes a supplementary component of the syndromes vector s=H·rT.
An example of such an iterative decoding algorithm is disclosed in the article by M. Sakata et al. entitled “Generalized Berlekamp-Massey Decoding of Algebraic-Geometric Codes up to Half the Feng-Rao Bound” (IEEE Trans. Inform. Theory, vol 41, pages 1762 to 1768, November 1995) This algorithm can be viewed as a generalization of the Berlekamp-Massey algorithm to algebraic geometric codes defined on a curve of non-zero genus.
Another example of an iterative decoding algorithm has been disclosed by M. O'Sullivan in the article “A Generalization of the Berlekamp-Massey-Sakata Algorithm” (preprint 2001).
For any received word r, the set of error locating polynomials defined above associated with the transmission errors affecting that word is termed is termed a “Gröbner ideal”. It is possible to generate this Gröbner ideal by means of a finite set of polynomials which constitutes what is known as a “Gröbner basis” of the ideal. The O'Sullivan algorithm which has just been cited produces such a “Gröbner basis” from a matrix S*, of dimension n×n, obtained by “extending” the matrix S (in other words the elements of S and those of S* are identical for j≦w(i) with i≦n−k). This extension is possible each time the number of errors in the received word is less than or equal to (n−k−g)/2.
Thus, when the number of errors in the received word is less than or equal to (n−k−g)/2, it is in general necessary, in order to be able to locate those errors, to know further elements of the syndromes matrix than the elements which we will qualify as “known” due to the fact that they are equal to components of the error syndromes vector s=H·rT or to simple linear combinations of those components (see the numerical example described below). It is fortunately possible to calculate these elements of “unknown” value by a method comprising a certain number of “majority decisions”, for example the algorithm known as the “Feng-Rao” algorithm (see article by G.-L. Feng and T. R. N. Rao entitled “Decoding Algebraic-Geometric Codes up to the Designed Minimum Distance>>, IEEE Trans. Inform. Theory, vol. 39, n° 1, January 1993). The object of this algorithm is essentially to extend the matrix S by means of calculation steps having the role of successive iterations. A number of iterations is necessary equal to a certain number g′, where g′ is at most equal to 2 g, in order to reach the state where, as explained above, it becomes possible to calculate a Gröbner basis from the matrix S* so obtained.
At this stage, it is also possible to calculate additional “unknown” elements of the matrix S* from elements obtained previously, either by means of new iterations of a “majority decisions” algorithm, or more conveniently by means of a certain number of relationships, known as “recursion” relationships, using “feedback polynomials” chosen from the Gröbner basis. In relation to this, reference can be made to the article by Sakata et al. cited above.
In the context of the present invention, it will be said that the elements of the syndromes matrix S* (“known” or “unknown”) are “extended error syndromes”.
The invention concerns more particularly the sub-step consisting of calculating the corrected value of the erroneous components of the received word; it thus concerns the algorithms adapted to provide an estimated value ê of the transmission error e suffered by the transmitted codeword.
The calculation of errors for algebraic geometric codes is prima facie more complicated than for Reed-Solomon codes. Thus:                the error locating sub-step not only produces one error locating polynomial (denoted above Λ(Z)), but several polynomials, which form a Gröbner basis of the ideal of the error locating polynomials;        these error locating polynomials are polynomials with two variables instead of one; and        these error locating polynomials thus possess partial derivatives with respect to those two variables, such that the Formey formula given above, which involves a single derivative, is no longer applicable.        
Various error calculating algorithms are known for algebraic geometric codes
The article “Algebraic Geometry Codes”, by Tom Høholdt, Jacobus Van Lint and Ruud Pelikaan (Chapter 10 of the “Handbook of Coding Theory”, North Holland, 1998) constructs the product of certain powers of the polynomials of the Gröbner basis. It then performs a linear combination of those products, allocated with appropriate coefficients. Finally it shows that the value of the polynomial so obtained, taken at the point (x,y) of the locating set is, with the sign being the only difference, the value of the error for the component of the received word labeled by that point (x,y).
The article “A Generalized Fomey Formula for Algebraic Geometric Codes” by Douglas A. Leonard (IEEE Trans. Inform. Theory, vol. 42, n° 4, pages 1263 to 1268, July 1996), and the article “A Key Equation and the Computation of Error Values for Codes from Order Domains” by John B. Little (published on the Internet on Apr. 7, 2003) calculate the values of the errors by evaluating a polynomial with two variables at the common zeros of the error locating polynomials.
These three algorithms are complex to implement, in particular due to the fact that they comprise the multiplication of the two variable polynomials, in addition to formal multiplications in Fq.
A simpler algorithm is known from the article “A Formey type formula for the determination of error values for Hermitian codes” by Ralf Kötter (Algebraic Decoding of Algebraic Geometry and Cyclic Codes, dissertation No. 419, Linkoping Studies in Science and Technology, 1996). However, this algorithm applies solely to the case of the codes constructed on a “hermitian” curve (i.e. a curve represented by the equation Y√{square root over (q)}+Y=X1+√{square root over (q)} defined over Fq, where q is a perfect square).
European patent application No. 03293336.8 in the name of CANON discloses a decoding method adapted in particular to “one-point” algebraic geometric codes defined on an algebraic curve of the kind C(a,b) (see above), and which performs both location and correction of errors.
This method relies on the subdivision of the locating set of the code into subsets which we will term “aggregates”. By definition, an “aggregate” groups together the pairs (x,y) of the locating set having a common value of x; these pairs will be denoted (x,yp(x)), where p=0, . . . , λ(x)−1 and λ(x) is the cardinal of the aggregate considered (naturally, it would be equally possible to define the aggregates and describe the decoding method according to the invention, by swapping the roles of the unknowns X and Y of the equation representing the algebraic curve on which the code is defined). The components of any received word c of length n will then be denoted c(x,yp(x)) when it is wished to emphasize the aggregate structure, and it will be stated that the components c, indexed for that purpose, which have the same value of x form an “aggregate of components” of the word c.
Let m be the maximum weight of the monomials defining the lines of the parity-check matrix (see above). According to application No. 03293336.8, these monomials are classified in sets of monomialsMj={YjXi|0≦i≦(m−bj)/a}
for j≧0, j<a, and j≦(m/b). The cardinal of this set Mj is thus:t(j)=1+INT [(m−bj)/a], and the maximum value of j, denoted jmax, satisfies:
      n    -    k    =            ∑              j        =        0                    j        max              ⁢                  t        ⁡                  (          j          )                    .      
Let x1,x2, . . . ,xμ denote the different values of x in the locating set, andv=[v(x1,y0(x1)), . . . , v(x1,yλ1−1(x1)), . . . , v(xμ,yλμ−1(xμ))],
denote any particular codeword for each aggregate attached to one of the values x1,x2, . . . ,xμ of x, there are constructed (jmax+1) “aggregate symbols”
            v      j        ⁡          (      x      )        ≡            ∑              p        =        0                              λ          ⁡                      (            x            )                          -        1              ⁢                            [                                    y              p                        ⁡                          (              x              )                                ]                j            ⁢              v        ⁡                  (                      x            ,                                          y                p                            ⁡                              (                x                )                                              )                    for j=0, . . . , jmax. These aggregate symbols serve to form (jmax+1) “aggregate words”vj≡[vj(x1),vj(x2), . . . ,vj(xμ)],of length μ.
It is easily verified that the condition of belonging to the algebraic geometric code (i.e. H·vT=0) is equivalent to the set of (jmax+1) equations:Ht(j)·vjT=0,where the function t(j) is given above and is, by definition,
      H    t    =            [                                    1                                1                                …                                1                                                              x              1                                                          x              2                                            …                                              x              μ                                                            ⋮                                ⋮                                ⋮                                ⋮                                                              x              1                              t                -                1                                                                        x              2                              t                -                1                                                          …                                              x              μ                              t                -                1                                                        ]        .  
The advantage of this formulation is that the matrix Ht of the equation is a Vandermonde matrix defined over Fq; consequently, if Ht(j) is considered as a parity-check matrix defining codewords vj, we have here, for each value of j, a Reed-Solomon code, for which decoding algorithms are known which are simple as well as providing good performance; For example, if a word r has been received, calculation is first made, for j=0, . . . , jmax, of the “aggregate received words”rj=[rj(x1),rj(x2), . . . ,rj(xμ)],in which, for x=x1,x2, . . . ,xμ, the “aggregate received words” rj(x) are given by
                    r        j            ⁡              (        x        )              =                  ∑                  p          =          0                                      λ            ⁡                          (              x              )                                -          1                    ⁢                                    [                                          y                p                            ⁡                              (                x                )                                      ]                    j                ⁢                  r          ⁡                      (                          x              ,                                                y                  p                                ⁡                                  (                  x                  )                                                      )                                ;next use is made of the Berlekamp-Massey algorithm for locating the erroneous symbols of each word rj, followed by the Formey algorithm for the correction of those erroneous symbols, according to the error syndromes vector sj=Ht(j)rjT.
Thus, during the error locating steps in the method according to application No. 03293336.8, erroneous aggregates associated with the received word are located, and not individual erroneous components of the received word. Because of this, the number of errors which can be corrected with this method may be less than the theoretical error correction capability of the code (as explained above, that theoretical capability is equal to INT[(d−1)/2], where d is the minimum distance of the algebraic geometric code considered).